/**
//给你一个数字数组 arr 。 
//
// 如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。 
//
// 如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
//
// 输入：arr = [3,5,1]
//输出：true
//解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。
// 
//
// 示例 2： 
//
// 输入：arr = [1,2,4]
//输出：false
//解释：无法通过重新排序得到等差数列。
// 
//
// 
//
// 提示： 
//
// 
// 2 <= arr.length <= 1000 
// -10^6 <= arr[i] <= 10^6 
// 
// Related Topics 数组 排序 👍 23 👎 0

*/

package com.xixi.basicAlgroithms.sort;
public class ID01502CanMakeArithmeticProgressionFromSequence {
public static void main(String[] args) {
Solution solution = new ID01502CanMakeArithmeticProgressionFromSequence().new Solution();
    System.out.println(solution.canMakeArithmeticProgression(new int[]{3,5,1}));
}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {


        //先快排
        quickSort(arr, 0, arr.length -1);

        //然后遍历对比是否差相等
        int diff = arr[1] - arr[0];

        for(int i = 1; i < arr.length; ++i){
            int nowDiff = arr[i] - arr[i-1];
            if(diff != nowDiff){
                return false;
            }
        }

        return true;
    }

    public int [] quickSort(int[] arr, int start, int pivot){
        if(start > pivot){
            return arr;
        }
        int pivotValue = arr[pivot];
        //快慢指针找到下一次的分割点
        int nextPivot = start;//初始化到当前分区的头部
        for(int i = start; i < pivot; ++i){//快指针遍历当前分区
            //如果遇到当前数值小于pivotValue的时候
            if(arr[i] < pivotValue){
                swap(arr,i, nextPivot);//将arr[i]当前值换到nextPivot的前面去
                nextPivot++;
            }
        }
        swap(arr,nextPivot, pivot);//将当前pivot的值和nextPivot交换，相当于把pivotValue放到正中间的位置，左边都是小于pivotValue的，右边都是大于等于pivotValue的

        //递归快排左右两个分区, 中间左边都是小于pivotValue的不用动
        quickSort(arr, start, nextPivot - 1);
        quickSort(arr, nextPivot + 1, pivot);

        return arr;

    }

    public void swap(int[] arr, int a, int b){
        int tmp = arr[b];
        arr[b] = arr[a];
        arr[a] = tmp;

    }
}
//leetcode submit region end(Prohibit modification and deletion)




}